package main

import (
	"sort"
	"strconv"
	"strings"
)

var _ = `
49. 字母异位词分组
中等
相关标签
相关企业
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。


示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]


提示：

1 <= strs.length <= 104
0 <= strs[i].length <= 100
strs[i] 仅包含小写字母
`

// 方法一
func getStrRoute(str string) string {
	chars := []rune(str)
	// 排序复杂度 nlog(n)
	sort.Slice(chars, func(i, j int) bool {
		return chars[i] < chars[j]
	})
	return string(chars)
}

func groupAnagrams(strs []string) [][]string {
	// 属于同一个字符集的，需要聚合到一起 => 需要根据聚合标准去聚合; 聚合标准 -> 根相同(顺序字母)
	m := make(map[string][]string)
	for _, str := range strs {
		route := getStrRoute(str)
		if _, ok := m[route]; ok {
			m[route] = append(m[route], str)
		} else {
			m[route] = []string{str}
		}
	}

	res := make([][]string, 0)
	for _, v := range m {
		res = append(res, v)
	}
	return res
}

// 方法二
func groupAnagrams2(strs []string) [][]string {
	// 属于同一个字符集的，需要聚合到一起 => 需要根据聚合标准去聚合; 聚合标准 -> 根相同(字母数)

	m := make(map[string][]string)
	for _, str := range strs {
		// 求字符的字母计数
		strCharCount := getStrCharCount(str)

		if _, ok := m[strCharCount]; ok {
			m[strCharCount] = append(m[strCharCount], str)
		} else {
			m[strCharCount] = []string{str}
		}
	}

	// 遍历输出
	res := make([][]string, 0)
	for _, v := range m {
		res = append(res, v)
	}
	return res
}

func getStrCharCount(str string) string {
	countMap := make(map[rune]int)
	chars := []rune(str)
	for _, chr := range chars {
		countMap[chr]++
	}

	// 按顺序返回计数
	strCounts := make([]string, 0)
	for i := int32('a'); i <= int32('z'); i++ {
		cnt := strconv.Itoa(countMap[rune(i)])
		strCounts = append(strCounts, cnt)
	}

	return strings.Join(strCounts, "-")
}

func main() {

}
